1. Field of the Invention
This invention relates to a method and apparatus for selecting attributes and their values.
2. Background Art
A system is comprised of components. Before a system can be built, the components of the system must be identified. To configure a system, a user must select a combination of components that are all compatible with one another. One who is knowledgeable about systems and their components defines a system. Thus, for example, an automobile salesperson assists an automobile buyer in determining the type and features of an automobile. The salesperson understands the features and options that are available to create a valid configuration. Some features and options cannot be combined. The selection of some features results in other features being unavailable. Without the assistance of a knowledgeable salesperson, it would be difficult for a buyer to identify appropriate combinations of components and to verify that they result in a valid configuration.
Computer systems have been developed to assist one in configuring a system. However, these systems sometimes use a configuration language to define a system. Like a programming language, a configuration language uses a syntax that must be understood by a user who is maintaining the data (i.e., a data maintainer). This limits the number of users who are able to use the configuration systems. That is, the level of sophistication needed to communicate with the configuration system (through the configuration language) results in less sophisticated users being unable to use the system.
In addition, configuration systems impose a flow or ordering to the user operations. For example, a user is often required to remove components from the system in reverse of the order in which they were chosen. Thus, in the course of removing an unwanted component from a configuration, a user may be forced to remove other components that the user wants to keep in the configuration. A novice user may have to perform many removal operations before achieving an acceptable configuration. If the novice user is required to remove components in a preset order, the user can become frustrated or confused and abort the configuration process.
Some systems are designed for a more sophisticated user possessing knowledge of the system to be configured as well as the configuration system for configuring the system. An end user, such as an automobile buyer, would have difficulty using these systems.
To use these systems, a user must be trained to understand the configuration language. Thus, a user who otherwise has knowledge of the systems that are being configured must undergo training to be able to use these configuration systems to configure systems. This leads to increased expenditures for training.
Some systems are intended for configuring systems where there are a relatively small number of possible configurations and where the interdependencies between component attributes are not complicated. Some types of systems, for example, apparatus used in an industrial plant, may be built on a custom or semi-custom basis. Since particular configurations of custom or semi-custom systems may never have been built before or may be produced very infrequently, it may not be possible for users to have experience with such systems. Thus, a technique is needed to allow appropriate custom or semi-custom systems to be configured by users who may have no experience with such systems.
The specifications for some types of systems, such as certain types of industrial apparatus, may have a large number of parameters to be specified when ordering the system or its components. Since each parameter may have numerous possible values, very large numbers of possible combinations of various attribute values may exist. However, not all possible combinations define valid system configurations. For example, the selection of certain values for certain parameters may prevent the choice of certain values for other parameters.
If there are many interdependencies between parameters, such that they limit the number of valid values for one parameter based on values chosen for other parameters, the number of valid combinations may be very small compared to the total number of possible combinations (valid plus invalid). If the range of possible combinations is considered to be a data range, those combinations in the data range that are valid may be referred to as a data set. If the data set is small relative to the data range, the data set is said to be sparse, as the data range is sparsely populated with valid data.
Traditional configuration techniques are generally inefficient for configuring systems in environments with sparse data sets. Any time or effort expended toward configuring invalid combinations is wasted and leads to inefficiency. Thus, a technique is needed for accurately configuring systems using sparse data sets.
The representation used by the method according to one embodiment of the present invention can be used to represent an arbitrary constraint network. Since solving arbitrary constraint networks is NP complete, it can be concluded that the problem addressed by the invention is NP complete. An NP complete problem is difficult because the number of possible solutions expands exponentially with respect to the number of variables to be solved. Such problems can be solved by examining all of the possible solutions if the number of variables is very small. However, as the number of variables and their possible values increases, a so-called combinatorial explosion occurs and the difficulty of solving the problem rapidly exceeds the total computational power available.
To successfully configure products and assemblies in realtime, a technique is needed to not only find a solution to the problem, but to do so rapidly. Thus, an exact solution to the problem of filtering values during configuration is not expected to be possible. Consequently, the present invention applies a heuristic approach to the problem, and the heuristic is optimized to increase its efficiency as directed toward the problem.
A heuristic is a technique that improves the efficiency of a search process, possibly by sacrificing claims of completeness. In this discussion, “complete” means that everything that is identified as being selectable is actually selectable. While heuristics may not always find the ideal solution to a problem, they provide practically useful solutions and increase the efficiency of finding such solutions. A heuristic approach is very useful for configuring products and assemblies, since a customer would be unwilling to wait an exponentially long time to be sure they are ordering the optimum product for their needs. Rather, a customer would prefer a quick solution that will meet its specifications. Since there is no guarantee that waiting an exponentially long time would yield a solution that is actually better than a quick solution provided by a heuristic, the long delay associated with calculating an exact solution cannot be justified.